class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if(n == 1)
            return 0;
        
        // start表示当前的覆盖范围
        int end = 0, start = 0, step = 0;

        for(int i = 0; i < n; i++)
        {
            end = max(end, i + nums[i]);
            if(i == start)
            {
                // 表示当前覆盖范围走完了
                step++;         // 步数加1
                start = end;    // 更新当前最远的覆盖范围
            }

            // 如果当前最远覆盖范围包含终点，则break返回
            if(start >= n - 1)
                break;
        }
        return step;

        // 下面时动态规划的做法
        // dp[i]表示到达i位置的最少跳跃次数
        // vector<int> dp(n, 0x3f3f3f3f);

        // // 初始化
        // dp[0] = 0;
        // for(int i = 1; i < n; i++)
        //     for(int j = 0; j < i; j++)
        //         if(i - j <= nums[j])
        //             dp[i] = min(dp[i], dp[j] + 1);
        // return dp[n - 1];
    }
};